﻿#define _CRT_SECURE_NO_WARNINGS
#include"fig.h"
extern int c[MAX];
void create(F* w) {
	w->side = 9;
	w->vertex = 15;
	w->a[0] = 'A';
	w->a[1] = 'B';
	w->a[2] = 'C';
	w->a[3] = 'D';
	w->a[4] = 'E';
	w->a[5] = 'F';
	w->a[6] = 'G';
	w->a[7] = 'H';
	w->a[8] = 'I';

	for (int i = 0; i < w->side; i++) {
		for (int j = 0; j < w->side; j++) {
			w->b[i][j] = 0;
		}
	}

	w->b[0][1] = 1;
	w->b[0][5] = 1;

	w->b[1][0] = 1;
	w->b[1][2] = 1;
	w->b[1][6] = 1;

	w->b[2][3] = 1;
	w->b[2][8] = 1;

	w->b[3][4] = 1;
	w->b[3][6] = 1;
	w->b[3][7] = 1;
	w->b[3][8] = 1;

	w->b[4][5] = 1;

	w->b[5][6] = 1;

	w->b[6][7] = 1;
	for (int i = 0; i < w->side; i++) {
		for (int j = 0; j < w->side; j++) {
			w->b[j][i] = w->b[i][j];
		}
	}
	for (int i = 0; i < w->side; i++) {
		c[i] = 0;
	}
}
void dfs(F* w, int i) {
	c[i] = 1;
	printf("%c ", w->a[i]);
	for (int j = 0; j < w->side; j++) {
		if (w->b[i][j] == 1 && c[j] == 0) {
			dfs(w, j);
		}
	}
}
void bfs(F* w, int p) {
	for (int i = 0; i < w->side; i++) {
		c[i] = 0;
	}
	A r;
	c[p] = 1;
	InitQueue(&r);
	printf("%c ", w->a[p]);
	EnQueue(&r, p);
	while (!QueueEmpty(&r)) {
		p = QueueFront(&r);
		OutQueue(&r);
		for (int j = 0; j < w->side; j++) {
			if (w->b[p][j] == 1 && c[j] == 0) {
				c[j] = 1;
				printf("%c ", w->a[j]);
				EnQueue(&r, j);

			}
		}
	}

}
void InitQueue(A* r) {
	r->a = r->b == NULL;
	r->x = 0;
}
bool QueueEmpty(A* r) {
	assert(r);
	return r->a == NULL;
}
x QueueFront(A* r) {
	assert(r);
	assert(r->a);
	return r->a->data;
}
void EnQueue(A* r, x a) {
	assert(r);
	QL* new = (QL*)malloc(sizeof(QL));

	if (new == NULL) {
		printf("malloc ʧ\n");
		exit(-1);
	}
	else {
		new->data = a;
		new->next = NULL;
		if (r->a == NULL) {
			r->a = r->b = new;
			r->x++;
		}
		else {
			r->b->next = new;
			r->b = r->b->next;
			r->x++;
		}
	}

}

void OutQueue(A* r) {
	assert(r);
	assert(r->b);
	if (r->a->next == NULL)
	{
		free(r->a);
		r->a = r->b = NULL;
		r->x--;
	}
	else
	{
		QL* new = r->a->next;
		free(r->a);
		r->a = new;
		r->x--;
	}
}
